package 纯数组;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-19
 **/

public class No334递增的三元子序列 {

    /**
     * 给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
     * 如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
     * <p>
     * 示例 1：
     * 输入：nums = [1,2,3,4,5]
     * 输出：true
     * 解释：任何 i < j < k 的三元组都满足题意
     * 示例 2：
     * 输入：nums = [5,4,3,2,1]
     * 输出：false
     * 解释：不存在满足题意的三元组
     * 示例 3：
     * 输入：nums = [2,1,5,0,4,6]
     * 输出：true
     * 解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6
     *  
     * 提示：
     * 1 <= nums.length <= 105
     * -231 <= nums[i] <= 231 - 1
     *  
     * 进阶：你能实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案吗？
     */

    // high level code
    public boolean increasingTripletGood(int[] nums) {
        // 维持一个第一小
        // 再维持一个第二小
        int minNum = Integer.MAX_VALUE;
        int midNum = Integer.MAX_VALUE;

        for (int num : nums) {
            if (num <= minNum) {
                minNum = num;
            } else if (num <= midNum) {
                midNum = num;
            } else {
                return true;
            }
        }

        return false;
    }

    // low level code
    public boolean increasingTriplet(int[] nums) {

        // 前方最小元素
        int[] minDp = new int[nums.length];
        // 后方最大元素
        int[] maxDp = new int[nums.length];

        minDp[0] = nums[0];
        maxDp[nums.length - 1] = nums[nums.length - 1];

        for (int i = 1; i < nums.length; i++) {
            minDp[i] = Math.min(minDp[i - 1], nums[i]);
        }

        for (int i = nums.length - 2; i >= 0; i--) {
            maxDp[i] = Math.max(maxDp[i + 1], nums[i]);
        }

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > minDp[i] && nums[i] < maxDp[i]) {
                return true;
            }
        }

        return false;
    }

}
